class Solution(object):
    def minDeletionSize(self, strs):
        m = len(strs)
        n = len(strs[0])
        st = [[i for i in range(m)]]
        c = 0
        j = 0
        while st and j < n:
            next_st = []
            flag = False
            for now_st in st:
                t = len(now_st)
                next_set = set()
                for i in range(t - 1):
                    if strs[now_st[i + 1]][j] < strs[now_st[i]][j]:
                        flag = True
                        break
                    if strs[now_st[i + 1]][j] == strs[now_st[i]][j]:
                        next_set.add(now_st[i])
                        next_set.add(now_st[i + 1])
                    if strs[now_st[i + 1]][j] > strs[now_st[i]][j]:
                        if next_set:
                            temp_st = list(next_set)
                            temp_st.sort()
                            next_st.append(temp_st)
                        next_set = set()
                if flag:
                    break
                if next_set:
                    temp_st = list(next_set)
                    temp_st.sort()
                    next_st.append(temp_st)
            if flag:
                c += 1
                j += 1
            else:
                st = next_st
                j += 1
        return c


data = Solution()
strs = ["za", "zb", "zc"]
print(data.minDeletionSize(strs))
strs = ["xc", "yb", "za"]
print(data.minDeletionSize(strs))
strs = ["zyx", "zvu", "zsr"]
print(data.minDeletionSize(strs))
